package leetcode_200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *@author 周杨
 *RepeatedDNASequences_187 寻找重复的10子串 对字符串进行编码
 *describe:AC 70%
 *2018年6月10日 下午4:58:16
 */
public class RepeatedDNASequences_187 {

	public static void main(String[] args) {
		RepeatedDNASequences_187 test=new RepeatedDNASequences_187();
		System.out.println(0xfffff);
		List<String> res=test.findRepeatedDnaSequences("AAAAAAAAAAA");
		//List<String> res=test.findRepeatedDnaSequences("AAAAAAAAAAAA");

	}
	
	/**
	 * describe:简单匹配 把字符串放进map里编码
	 * 2018年6月10日 下午7:30:41
	 */
	public List<String> findRepeatedDnaSequences(String s) {
		List<String> res=new ArrayList<String>();
        Map<String,Integer> map=new HashMap<String,Integer>();
        for(int i=0;i<s.length()-9;++i) {
        	String str=s.substring(i, i+10);
        	Integer count=map.get(str);
        	if(count==null)
        		map.put(str, 1);
        	else {
        		if(!res.contains(str))
        			res.add(str);
        	}
        }
        return res;
    }
	
	/**
	 * describe:
	 * 	字符串只包含A,C,G,T四个字母，观察这四个字母的ascii码，A的二进制ascii码为 0100 0001，C为0100 0011，G为0100 0111，T为0100 0111，
	 * 	发现每个字母二进制的低三位都不一样，因此可以使用这三位去表示一个字母，那么一个子字符串有10个字母，那么就可以使用30位二进制位去表示这个子字符串，
	 * 	为了可以提取出后30位，可以使用0x7FFFFFFF(或者0x3FFFFFFF)掩码去提取。
	 * 	当从S中取出第九个字符时，那么就会得到从字符串S中第一个子字符串的哈希值，那么将其存到哈希表中（将值加1），
	 * 	之后每向左移动3位替换一个字符，得到新的字符串哈希值，
	 * 	那么在哈希表中寻找哈希表中该值是否为1，如果为1，那么就说明这个子字符串已经在前面出现，同时加1,可以避免将相同的子字符串放到结果中
	 * 	2018年6月10日 下午7:31:29
	 */
	public List<String> findRepeatedDnaSequences1(String s){
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 10) {
            return res;
        }
        //对字母进行编码
        char[] map = new char[256];
        map['A'] = 0;
        map['C'] = 1;
        map['G'] = 2;
        map['T'] = 3;
        int mask = 0xfffff;//20bit,10个字母，每个字母占2bit
        int val = 0;
        char[] schar = s.toCharArray();
        for (int i = 0;i < 9 ;i ++ ) {//对前9位进行编码
            val = (val << 2) | (map[schar[i]] & 3);
        }
        byte[] bytes = new byte[1 << 20];
        for (int i = 9;i < schar.length ;i ++ ) {
        //注意这里与mask&,超出部分截取
            val = ((val << 2) & mask) | ((map[schar[i]]) & 3);//编码
            if (bytes[val] == 1) {
                res.add(String.valueOf(schar,i - 9,10));
            }
            //这里很关键,字节大小有限，若超过限制变为1，会重复加
            if (bytes[val] < 2)   bytes[val]++;
        }
        return res;
    }

}
